import java.util.*;

class Solution4 {
    public List<List<Integer>> getSkyline(int[][] buildings) {

        //定义集合x，添加建筑物所有涉及的x坐标
        Set<Integer> x = new TreeSet<Integer>();
        for(int[] i : buildings) {
            x.add(i[0]);
            x.add(i[1]);
        }

        //定义优先队列（堆），上大下小，存放建筑物的高度和边缘坐标
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>((a, b) -> b[1] - a[1]);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        int cul = 0;
        for(int xi : x) {
            //左边x轴大于等于xi，入队
            while(cul < buildings.length && buildings[cul][0] <= xi) {
                queue.offer(new int[]{buildings[cul][1], buildings[cul][2]});
                cul++;
            }
            //右边x轴小于等于xi，出队
            while(!queue.isEmpty() && queue.peek()[0] <= xi) {
                queue.poll();
            }
            //取高度加入返回列表
            int max = queue.isEmpty() ? 0 : queue.peek()[1];
            if(result.size() == 0 || max != result.get(result.size() - 1).get(1) ) {
                result.add(Arrays.asList(xi, max));
            }
        }
        return result;
    }
}